#include <vector>
using namespace std;
class Solution
{
public:
    int rob(vector<int> &nums)
    {
        int size(nums.size());
        if (size == 1)
            return nums[0];
        vector<int> add(size, 0);
        add[0] = nums[0];
        // 每个点的由来根据题意写
        // 每个点都可能从[开始,他之前-2]来,选择一个最佳路线
        // 这个点的值就是最佳路线+这个房子里的钱
        for (int i = 1; i < size; i++)
        {
            int max_from(0);
            for (int j = i - 2; j >= 0; j--)
            {
                max_from = max(add[j], max_from);
            }
            add[i] = nums[i] + max_from;
        }
        return max(add[size - 2], add[size - 1]);
    }
};
// 2 7 9  3  1
// 2 7 11 10 12